03 贝尔曼最优公式

Optimal Policy

如果对于任意 $s$ 、任意策略 $\pi$ ，某个策略 $\pi^*$ 都保证

v_{\pi^*}(s) \ge v_\pi(s)

则 $\pi^*$ 是最优策略。

从这里来看，最优策略是通过状态价值判断的；此外，这里的最优指策略在每种状态下都最优。

BOE

贝尔曼公式为

v(s) = \mathop{\Sigma}\limits_{a}\pi(a|s)(\mathop{\Sigma}\limits_{r}p(r|s,a)r + \gamma \mathop{\Sigma}\limits_{s\prime}p(s\prime|s,a)v(s\prime))

此时策略是给定的。在策略不确定的情况下，对贝尔曼公式取最大值，就得到了贝尔曼最优公式（BOE）。

v(s) = \mathop{max}\limits_{\pi}\mathop{\Sigma}\limits_{a}\pi(a|s)q(s,a)

矩阵形式为

v(s) = \mathop{max}\limits_{\pi}(r_\pi + \gamma P_\pi v)

求解思路

对于

v(s) = \mathop{max}\limits_{\pi}\mathop{\Sigma}\limits_{a}\pi(a|s)q(s,a)

如果 $q(s,a)$ 是给定的，可以认为 $\pi(a|s)$ 代表权重。这种情况下，考虑到

\mathop{\Sigma}\limits_{a}\pi(a|s) = 1

有

\mathop{max}\limits_{\pi}\mathop{\Sigma}\limits_{a}\pi(a|s)q(s,a) = \mathop{max}\limits_{a\in A(s)}q(s,a)

此时对应的策略为

\pi(a|s) = \begin{cases} 1,~a = a^* \\ 0,~a \ne a^* \end{cases} ~~~ a^* = arg~max_aq(s,a)

BOE求解

可以将BOE公式写成

v(s) := \mathop{max}\limits_{\pi}(r_\pi + \gamma P_\pi v)

将等号右边视作函数，则有

v = f(v)

压缩映射定理

如果 $f(x) = x$ ，则 $x$ 是 $f$ 的不动点。

如果对于任意不同 $x_1, x_2$ ，有

||f(x_1) - f(x_2)|| \le \gamma ||x_1 - x_2||, \gamma \in (0, 1)

则 $f$ 为压缩映射。

（这里的 $||\cdot||$ 可以是任何范式）

压缩映射定理指，对于任何形如 $x = f(x)$ 的等式，如果 $f$ 为压缩映射，有

存在性：有一个不动点 $x^*$ 满足 $x^* = f(x^*)$
唯一性：不动点 $x^*$ 是唯一的
算法：令 $x_{k + 1} = f(x_k)$ ， $k$ 趋于无穷时 $x$ 趋于 $x^*$

对于BOE中的 $v = f(v)$ ，可以证明 $f$ 是压缩映射。此时可以通过迭代求出 $v^*$ 的唯一解。

这里的 $v = f(v)$ 实际上是对于策略

\pi(a|s) = \begin{cases} 1,~a = a^* \\ 0,~a \ne a^* \end{cases} ~~~ a^* = arg~max_aq(s,a)

的特殊贝尔曼公式。

可以通过最优策略的定义证明，这种 $\pi^*$ 是最优的。

最优策略性质

当 $\gamma$ 接近1时，agent会较为远视；减小 $\gamma$ 时，agent会变得近视。

此外，显然，改变奖励也会改变策略。

最优策略不变性

如果对所有奖励 $r$ 进行仿射变换，即

r\prime = ar + b

此时最优状态价值 $v\prime$ 是原来 $v$ 的仿射变换

v\prime = av + b / (1 - \gamma)

此时，最优策略不变。